链表——复制含有随机指针的链表

Posted on | In ,

题目：随机指针是指指针的指向是随机的。

实现：利用HashMap的key-value结构

  1. 将所有链表的值进行复制，利用HashMap结构
  2. 将所有指针进行复制1’.next = 2’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.HashMap;
public class CopyListWithRand {
	/**
	 * 复制含有随机指针的链表，利用哈希表结构（HashMap）来存储
	 * @param head
	 * @return
	 */
	public static Node copyListWithRand(Node head) {
		HashMap<Node, Node> map = new HashMap<>();
		Node cur = head;
		//1. 将所有的值进行复制
		while(cur != null) {
			map.put(cur, new Node(cur.data)); //value是根据cur重新生成的对象
			cur = cur.next;
		}
		cur = head;
		//2. 将所有的指针进行复制:1'.next = 2'
		while (cur != null) {
			map.get(cur).next = map.get(cur.next);
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		return map.get(head); //返回map结构的头节点
	}
}